This invention relates to an access method and apparatus for selectively extracting or updating subarrays of a larger array stored in a modified word organized random access memory, and more particularly, relates to the modifications to a conventional word organized memory used for image processing.
A digital image is considered to be a two-dimensional array of image points, each of which comprises an integer or a set of integers. Image manipulation ideally includes the capability of storing an image array in a memory and operating upon selected clusters of points simultaneously, such as sequences of points in a single row or column of the array and points within a small rectangular area. This imposes the constraint that the memory must allow all points in any selected cluster to be accessed in one memory cycle. If any desired combination of points in the array could be accessed simultaneously from a bit addressable memory, then storage and retrieval of clusters of image points would pose no problem. However, because digital images form large arrays, only word organized memories are economically available. A conventional word organized memory includes a plurality of randomly accessible "words" of storage locations, each word of which can store a cluster of image points. However, it is necessary to modify the accessing mechanism of this conventional memory in order to permit access to clusters of image points when the points are not all in the same word of storage.
An image can be represented by an M .times. N array I(*,*) of image points, where each point I(i,j) for 0.ltoreq.i&lt;M and 0.ltoreq.j&lt;N is an integer or a set of integers which represents the color and intensity of a portion of the image. For simplicity, attention can be restricted to black/white images, for which I(i,j) is a single bit of information. Typically, I(i,j)=1 represents a black area of the image, and I(i,j)=0 represents a white area.
Images are most commonly generated by scanning pictorial data, such as that from documents. Thereafter, these images can be stored, viewed from a display, transmitted, or printed. Since most scanners and printers process an image from top to bottom and from left to right, images are normally transmitted in the standard "row major" sequence: I(0,0), I(0,1), . . ., I(0,N1), I(1,0), . . ., I(M1,N1). Therefore, a memory system for image processing operations should at least permit simultaneous access to a number of adjacent image points on a single row of I(*,*). This would permit the image or a partial image to be transferred rapidly into and out of the memory system, with many image points in each row being transferred simultaneously.
For image processing operations, such as character recognition, it is necessary to rotate an image or a partial image by a multiple of ninety degrees. Such rotations are greatly facilitated by a memory system that permits simultaneous access to a number of adjacent points along any row or column of the image array I(*,*). A memory system that permits such accesses can be used to rotate by ninety degrees (counter-clockwise) an image transmitted in row major sequence. This is attained by (1) the transfer of the image into the memory row by row, starting with the uppermost row and storing many image points in each row simultaneously; and (2) the transfer of the image out of the memory column by column, starting with the rightmost column and retrieving many image points in each column simultaneously.
It is also desirable to access rectangular blocks of points within an image to accommodate another class of image processing operations, such as block insertion, block extraction, and contour following. For example, it may be desirable to add alphanumeric characters to the image from a stored dictionary, which dictionary includes a predefined bit array for each character. Similarly, it may be desirable to delete or edit characters or other rectangular blocks from an image. Lastly, algorithms for locating the contours of objects in the image involve moving a cursor from one image point to another along a border or boundary of an object. The contour following algorithms require rapid access to an image point and a plurality of its near neighbors, which together constitute a block of image points.
Typically, a word organized random access memory comprises a plurality of memory modules, each module being a storage device with a plurality of randomly accessible storage cells. Although each cell is able to store an image point which comprises a single bit of information, only one cell in a module can be accessed (read from or stored into) at a time. The accessing mechanism of a conventional word organized random access memory provides a single cell address to all of its constituent memory modules, so that the ith cell in one module can be accessed only in conjunction with the ith cell of all other modules. These cells together comprise the ith word of the memory. A conventional word organized random access memory thus provides access to a cluster of image points only if they are all stored in the same word of the memory. However, a suitable modification of the accessing mechanism for a word oranized memory can permit access to any desired cluster of image points, provided each module stores at most one point in the cluster.
As previously stated, a memory system is desired which permits simultaneous access to horizontal sequences, vertical sequences, and rectangular blocks of image points. If the desired horizontal and vertical sequences include pq image points, and if the dimensions of the desired blocks of image points are p .times. q, then a memory system with at least pq memory modules is required. Furthermore, a method for distributing the image points of an image array I(*,*) among memory modules must be designed which places the pq elements of each 1 .times. pq, pq .times. 1, or p .times. q subarray of I(*,*) in distinct modules. It is necessary to design accessing circuitry which permits simultaneous access to these subarrays, and which arranges their elements into a convenient order, such as row major order.
To minimize the cost of a memory system for image processing, it is desirable to limit the number of memory modules in the memory system to the minimum number. At least pq memory modules are required, since each of the desired subarrays comprises pq image points. However, it can be shown that no memory system with only pq memory modules can permit access to all 1 .times. pq, pq .times. 1, and p .times. q subarrays of an image array I(*,*). For this reason, some previously described memory systems have been restricted to pq memory modules and hence have not provided access to all of these subarrays. It was previously believed that the circuitry required to access stored subarrays is quite complicated unless p,q, and the number of memory modules are all powers of two, and hence that at least 2pq memory modules are required. Copending application Ser. No. 554,782, filed Mar. 3, 1975 now U.S. Pat. No. 3,995,253, discloses a memory system with precisely 2pq memory modules that permits access to all of the desired subarrays of I(*,*). The present invention describes a memory system that needs only pq+1 memory modules to provide access to all of these subarrays, namely, all 1 .times. pq subarrays, all pq .times. 1 subarrays, and all p .times. q subarrays.